Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever.
This invention pertains to the field of networking, and more particularly to Internet routing protocols.
Congestion at the links and in the routers is the main cause of large delays in the Internet. The approaches proposed to date for minimizing congestion fall in two categories: minimizing link delays in the network and server load balancing.
The conventional approach to minimizing link delays in computer networks consists of using a heuristic to compute a single shortest path from a source to a destination. Routing algorithms based on single shortest-path heuristics are very responsive to topological and link-cost changes, making them far more preferable than optimal routing for implementation in real networks. However, except under light traffic loads, the delays obtained with this type of routing are far from optimal. Furthermore, if link costs are associated with delays, single-path routing exhibits oscillatory behavior and becomes unstable as traffic loads increase.
Many optimal routing algorithms for minimizing link delays exist (also known as minimum-delay routing algorithms), but they all assume the input traffic and the network topology are stationary or very slowly changing, and require global constants that guarantee convergence. This makes optimal routing algorithms impractical for real networks given the bursty nature of traffic at any time scale, the random occurrences of topology changes, and the impossibility of determining global time constants that work for all input-traffic patterns.
With server load-balancing, a computation is assigned to a server based on the current computational load on various other servers, possibly with provisions for failover to handle the loss of a server or communication link. Commercial products typically use round robin, least number of connections, weighted priority, and server load or response time to determine how to distribute traffic among servers, but treat server load and network load separately.
With the widespread use of Internet technology and the affordability of computing hardware today, it is desirable to distribute processing elements (servers) over a network or internet to perform a wide variety of computing services. By doing so, third parties can maintain the servers and the network accessed by users, such that users do not have to worry about system management and need not know where in the network the services are provided.
Since congestion at the links and in the routers is the main cause of large delays, a routing method is more effectively optimized when congestion at both links and at routers is considered. No approaches to date, however, have been presented for the joint minimization of congestion at the links and servers of a network.
A method for determining the cost of routing data is described herein, where a communication cost for routing data from a current node to a successor node over a communication channel is computed, and then a processing node cost for processing data at the current node is computed, where the processing node cost represents a ratio of data input rates to data output rates at the current node. The two computations are combined to formulate a link cost for the current node, or the cost of routing data through that node, where the link cost can then be used in a routing algorithm for routing data.